#pragma once
#include"public_struct.h"
int countPrimes(int n) {
	if (n < 2)return 0;
	vector<int> v(5000005);
	int result = 0;
	for (int i = 2; i < n; ++i) {
		if (!v[i]) {
			++result;
		}
		else {
			continue;
		}
		int time = 2;
		while (time*i < n) {
			v[time*i] = 1;
			++time;
		}
	}
	return result;
}
